package com.lnn.algorithm.tabu;


import com.lnn.pojo.Node;
import com.lnn.pojo.Route;
import com.lnn.util.Address;
import com.lnn.util.Matrix;
import org.springframework.web.multipart.MultipartFile;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.Random;

/**
 * 禁忌搜索算法实现类
 *
 * @author: Li Ning Ning
 * @time: 2021/8/2 9:49
 * @description: TODO
 * @version: 1.0
 */
public class Tabu {

    /**
     * 城市数量
     */
    private int cityNum;

    /**
     * 迭代次数
     */
    private int iterMax;

    /**
     * 每次搜索邻居个数
     */
    private int neighbourNumber;

    /**
     * 禁忌长度
     */
    private int tabuLength;

    /**
     * 距离矩阵
     */
    private int[][] distance;

    /**
     * 最佳出现代数
     */
    private int bestIter;

    /**
     * 初始路径编码
     */
    private int[] route;

    /**
     * 初始路径长度
     */
    private int routeLength;

    /**
     * 最佳路径
     */
    private int[] bestRoute;

    /**
     * 最佳长度
     */
    private int bestRouteLength;

    /**
     * 禁忌表
     */
    private int[][] tabu;

    /**
     * 最佳路径地址
     */
    private String[] address;

    /**
     * 城市坐标x
     */
    private int[] x;

    /**
     * 城市坐标y
     */
    private int[] y;
    private Random random;

    public Tabu() {

    }

    public Tabu(int iterMax, int neighbourNumber, int tabuLength) {
        this.iterMax = iterMax;
        this.neighbourNumber = neighbourNumber;
        this.tabuLength = tabuLength;
    }

    public Tabu(int cityNum, int iterMax, int neighbourNumber, int tabuLength) {
        this.cityNum = cityNum;
        this.iterMax = iterMax;
        this.neighbourNumber = neighbourNumber;
        this.tabuLength = tabuLength;
    }

    /**
     * 初始化参数
     *
     * @param distance 距离矩阵
     * @param address  位置数组
     */
    public Tabu init(int[][] distance, String[] address) {
        //初始化距离矩阵
        this.distance = distance;
        //初始化地址
        this.address = address;
        //初始化参数
        initParams();
        return this;
    }

    /**
     * 文件初始化参数
     */
    public Tabu init(MultipartFile multipartFile) throws IOException {
        // 读取数据
        File file = new File(Objects.requireNonNull(multipartFile.getOriginalFilename()));
        readFile(multipartFile, file);

        String strBuff;
        BufferedReader data = new BufferedReader(new InputStreamReader(
                new FileInputStream(file)));
        //初始化城市总数
        String temp = data.readLine();
        this.cityNum = Integer.parseInt(temp);
        distance = new int[cityNum][cityNum];
        x = new int[cityNum];
        y = new int[cityNum];
        address = new String[cityNum];
        for (int i = 0; i < cityNum; i++) {
            address[i] = "Node" + i;
        }
        //初始化城市坐标
        for (int i = 0; i < cityNum; i++) {
            strBuff = data.readLine();
            String[] strCol = strBuff.split(" ");
            x[i] = Integer.parseInt(strCol[1]);
            y[i] = Integer.parseInt(strCol[2]);
        }
        // 计算距离矩阵
        this.distance = Matrix.computeDistanceMatrix(x, y);
        initParams();
        return this;
    }

    private void readFile(MultipartFile multipartFile, File file) {
        int n;
        try (InputStream in = multipartFile.getInputStream(); OutputStream os = new FileOutputStream(file)) {
            // 得到文件流。以文件流的方式输出到新文件
            byte[] buffer = new byte[4096];
            while ((n = in.read(buffer, 0, 4096)) != -1) {
                os.write(buffer, 0, n);//写入文件
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 初始化参数
     */
    private void initParams() {
        //初始化路径
        route = new int[cityNum + 1];
        //初始化路径长度
        routeLength = Integer.MAX_VALUE;
        //初始化最优路径
        bestRoute = new int[cityNum + 1];
        //初始化最优路径长度
        bestRouteLength = Integer.MAX_VALUE;
        //初始化禁忌目录
        tabu = new int[tabuLength][cityNum + 1];
        //初始化最优迭代次数
        bestIter = 0;
        //初始化随便变量
        random = new Random(System.currentTimeMillis());
    }

    /**
     * 多次迭代路径
     *
     * @return 路径列表
     */
    public ArrayList<Route> solve() {
        // 初始化编码Ghh
        initRoute();
        //计算初始路径长度
        routeLength = evaluate(route);
        //保存初始路径到前最好路径
        copyRoute(route, bestRoute);
        //保存最好路径长度
        bestRouteLength = routeLength;
        int iter = 0;
        while (iter < iterMax) {
            int number = 0;
            int localEvaluation = Integer.MAX_VALUE;
            int[] localRoute = new int[cityNum + 1];
            while (number < neighbourNumber) {
                int[] neighbourRoute = generateNeighbour(route);// 得到当前编码rout的邻域
                if (judge(neighbourRoute) == 0) {// 判断编码是否在禁忌表中
                    int neighbourRouteLength = evaluate(neighbourRoute);
                    if (neighbourRouteLength < localEvaluation) {
                        copyRoute(neighbourRoute, localRoute);
                        localEvaluation = neighbourRouteLength;
                    }
                    number++;
                }
            }
            if (localEvaluation < bestRouteLength) {
                bestIter = iter;
                copyRoute(localRoute, bestRoute);
                bestRouteLength = localEvaluation;
            }
            copyRoute(localRoute, route);
            addTabu(localRoute);// 解禁忌表，localRoute加入禁忌表
            iter++;
        }
        ArrayList<Route> routes = formatData();
        printOptimal();
        return routes;
    }

    /**
     * 初始化编码initRoute
     */
    void initRoute() {
        int i, j;
        route[0] = random.nextInt(65535) % cityNum;
        for (i = 1; i < cityNum; ) {
            route[i] = random.nextInt(65535) % cityNum;
            for (j = 0; j < i; j++) {
                if (route[i] == route[j]) {
                    break;
                }
            }
            if (j == i) {
                i++;
            }
        }
    }

    /**
     * 复制编码体，复制编码src到dest
     *
     * @param src  源数组
     * @param dest 目的数组
     */
    public void copyRoute(int[] src, int[] dest) {
        System.arraycopy(src, 0, dest, 0, src.length);
    }

    /**
     * 评估，计算距离
     *
     * @param route 编码数组
     * @return 评估值，距离
     */
    public int evaluate(int[] route) {
        int len = 0;
        for (int i = 1; i < cityNum; i++) {
            len += distance[route[i - 1]][route[i]];
        }
        len += distance[route[cityNum - 1]][route[0]];
        return len;
    }

    /**
     * 邻域交换，得到邻居
     *
     * @param route 编码数组
     * @return 领域数组
     */
    public int[] generateNeighbour(int[] route) {
        int[] res = Arrays.copyOf(route, route.length);
        int random1 = random.nextInt(65535) % cityNum;
        int random2 = random.nextInt(65535) % cityNum;
        while (random1 == random2) {
            random2 = random.nextInt(65535) % cityNum;
        }
        int temp = res[random1];
        res[random1] = res[random2];
        res[random2] = temp;
        return res;
    }

    /**
     * 判断编码是否在禁忌表中
     *
     * @param route 源编码
     * @return 0：禁忌表中不存在该编码，1：禁忌表中存在该编码
     */
    public int judge(int[] route) {
        int i, j;
        for (i = 0; i < tabuLength; i++) {
            int flag = 0;
            for (j = 0; j < cityNum; j++) {
                if (route[j] != tabu[i][j]) {
                    flag = 1;// 不存在相同的禁忌表
                    break;
                }
            }
            if (flag == 0) {
                break;
            }
        }
        if (i == tabuLength) {
            return 0;// 不存在
        } else {
            return 1;// 存在
        }
    }

    /**
     * 解禁忌与加入禁忌
     *
     * @param route 需要加入禁忌表的编码
     */
    public void addTabu(int[] route) {
        int i, j, k;
        // 删除禁忌表第一个编码，后面编码往前挪动
        for (i = 0; i < tabuLength - 1; i++) {
            for (j = 0; j < cityNum; j++) {
                tabu[i][j] = tabu[i + 1][j];
            }
        }

        // 新的编码加入禁忌表
        for (k = 0; k < cityNum; k++) {
            tabu[tabuLength - 1][k] = route[k];
        }
    }

    private ArrayList<Route> formatData() {
        bestRoute = Address.StartAtZero(bestRoute);
        address = Address.arrayToAddress(bestRoute, address);
        ArrayList<Route> routes = new ArrayList<>();
        for (int i = 0; i < bestRoute.length; i++) {
            Route route = new Route();
            route.setNumber(bestRoute[i]);
            route.setAddress(address[i]);
            route.setDistance(distance[bestRoute[i]][bestRoute[(i + 1) % bestRoute.length]]);
            route.setTotalCity(address.length - 1);
            route.setTotalDistance(bestRouteLength);
            if (x != null && y != null) {
                route.setNode(new Node(x[bestRoute[i]], y[bestRoute[i]]));
            }
            routes.add(route);
        }
        return routes;
    }

    private void printOptimal() {
        System.out.println("禁忌搜索算法: ");
        System.out.println("The optimal length is: " + bestRouteLength);
        System.out.println("The optimal tour is: ");
        for (int i = 0; i < cityNum + 1; i++) {
            System.out.print(bestRoute[i] + " ");
        }
        System.out.println();
    }


}

